function maxSubArray2(nums: number[]): number {
  // dp, 当前连续值最大值
  // const dp: number[] = [];
  // 状态改变控制, 要不是我自己，要不就是跟上个连续的最大值进行相加，比较它们
  // dp[i] = max(dp[i], dp[i-1]+dp[i])

  // 初始值
  let prev = nums[0];
  // 存入比较值
  let max = nums[0];

  // 循环修改状态
  for (let i = 1; i < nums.length; i++) {
    prev = Math.max(nums[i], prev + nums[i]);
    max = Math.max(max, prev)
  }

  return max;
}

console.log(maxSubArray2([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maxSubArray2([1]));
console.log(maxSubArray2([5, 4, -1, 7, 8]));
